class Solution {
    public int firstMissingPositive(int[] nums) {
        // 归位法  o(n)复杂度找缺失的排序数字
        int len = nums.length;
        for(int i = 0; i< len; i++) {
            while(nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) { // 没有被归位就归位 已经在自身位置算是已经归位了的
                swap(nums, i, nums[i] - 1);
            }
        }

        for(int i = 0; i< len; i++) {
            if(nums[i] != (i + 1)) {
                return i + 1;
            }
        }
        return len + 1;
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}